/*
 * @Author: sympsel sympsel@outlook.com
 * @Date: 2025-07-24 19:19:03
 * @LastEditors: sympsel sympsel@outlook.com
 * @LastEditTime: 2025-07-25 22:56:21
 * @FilePath: \work25_7_24\src\Sort.c
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */
#include "Sort.h"

// 选择排序
void SelectSort(int* arr, int n) {
    if (n <= 1) {
        return;
    }
    for (int i = 0; i < n; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[minIndex] > arr[j]) {
                minIndex = j;
            }
        }
        SWAP(int, arr[minIndex], arr[i]);
    }
}


// 堆排序
void AdjustDwon(int* arr, int n, int root) {
    int child = root * 2 + 1;
    while (child < n) {
        if (child + 1 < n && arr[child + 1] > arr[child]) {
            child++;
        }

        if (arr[child] > arr[root]) {
            SWAP(int, arr[child], arr[root]);
            root = child;
            child = root * 2 + 1;
        } else {
            break;
        }
    }
}

void HeapSort(int* arr, int n) {
    for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
        AdjustDwon(arr, n, i);
    }

    for (int i = n - 1; i >= 0; i--) {
        SWAP(int, arr[0], arr[i]);
        AdjustDwon(arr, i, 0);
    }
}

void InsertSort(int* arr, int n) {
    for (int i = 0; i < n; i++) {
        int min = arr[i];
        int j = i - 1;
        for (; j >= 0; j--) {
            if (arr[j] > min) {
                arr[j + 1] = arr[j];
            } else {
                break;
            }
        }
        arr[j + 1] = min;
    }
}

void shell(int* arr, int n, int gap) {
    for (int i = gap; i < n; i++) {
        int min = arr[i];
        int j = i - gap;
        for (; j >= 0; j -= gap) {
            if (arr[j] > min) {
                arr[j + gap] = arr[j];
            } else {
                break;
            }
        }
        arr[j + gap] = min;
    }
}

void ShellSort(int* arr, int n) {
    int gap = n;
    while (gap > 1) {
        gap /= 2;
        shell(arr, n, gap);
    }
}

// 冒泡排序
void BubbleSort(int* arr, int n) {
    for (int i = 0; i < n - 1; i++) {
        bool flag = true;
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                SWAP(int, arr[j], arr[j + 1]);
                flag = false;
            }
        }
        if (flag) {
            break;
        }
    }
}

void BubbleSort2(int* arr, int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            if (arr[i] > arr[j]) {
                SWAP(int, arr[i], arr[j]);
            }
        }
    }
}

void Merge(int* arr, int left, int mid, int right) {
    int len = right - left + 1;
    int* temp = MALLOC(int, len);
    int i = left, j = mid + 1, k = 0;
    while (i <= mid && j <= right) {
        temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
    }
    while (i <= mid) {
        temp[k++] = arr[i++];
    }
    while (j <= right) {
        temp[k++] = arr[j++];
    }
    for (int i = 0; i < len; i++) {
        arr[left + i] = temp[i];
    }
    free(temp);
}

void MergeSortInner(int* arr, int left, int right) {
    if (left >= right) {
        return;
    }
    int mid = left + (right - left) / 2;
    MergeSortInner(arr, left, mid);
    MergeSortInner(arr, mid + 1, right);
    Merge(arr, left, mid, right);
}

void MergeSort(int* arr, int n) {
    MergeSortInner(arr, 0, n - 1);
}

void MergeSortNor(int* arr, int n) {
    for (int gap = 1; gap < n; gap *= 2) {
        for (int left = 0; left < n; left += gap * 2) {
            int mid = min(left + gap - 1, n - 1);
            int right = min(mid + gap, n - 1);
            Merge(arr, left, mid, right);
        }
    }
}

// 快速排序递归实现
// 快速排序hoare版本
int Partition1(int* arr, int left, int right) {
    int base = arr[left];
    int temp = left;
    while (left < right) {
        while (left < right && base <= arr[right]) {
            right--;
        }
        while (left < right && arr[left] <= base) {
            left++;
        }
        SWAP(int, arr[left], arr[right]);
    }
    SWAP(int, arr[left], arr[temp]);
    return left;
}
// 快速排序挖坑法
int Partition2(int* arr, int left, int right) {
    int base = arr[left];
    while (left < right) {
        while (left < right && base <= arr[right]) {
            --right;
        }
        arr[left] = arr[right];
        while (left < right && arr[left] <= base) {
            ++left;
        }
        arr[right] = arr[left];
    }
    arr[left] = base;
    return left;
}
// 快速排序前后指针法
int Partition3(int* arr, int left, int right) {
    int prev = left;
    int cur = left + 1;
    while (cur <= right && ++prev != cur) {
        if (arr[cur] < arr[left]) {
            SWAP(int, arr[prev], arr[cur]);
        }
        cur++;
    }
    return prev;
}
// 快速排序三路划分法
int Partition4(int* arr, int left, int right) {
    // 使用left作为基准值索引
    int cur = left + 1;
    while (cur <= right) {
        if (arr[cur] < arr[left]) {
            SWAP(int, arr[cur], arr[left]);
            cur++;
            left++;
        } else if (arr[cur] > arr[left]) {
            SWAP(int, arr[cur], arr[right]);
            right--;
        } else {
            cur++;
        }
    }
    return left;
}

void QuickSortInner(int* arr, int left, int right, int (*partition)(int*, int, int)) {
    if (left >= right) {
        return;
    }
    int baseIndex = partition(arr, left, right);
    QuickSortInner(arr, left, baseIndex - 1, partition);
    QuickSortInner(arr, baseIndex + 1, right, partition);
}

void QuickSort(int* arr, int n, int (*partition)(int*, int, int)) {
    QuickSortInner(arr, 0, n - 1, partition);
}

void QuickSortNor(int* arr, int n, int (*partition)(int*, int, int)) {
    // 非递归实现
        Stack* stack = StackInit();
        int left = 0;
        int right = n - 1;
        int baseIndex = partition(arr, left, right);
        if (baseIndex > left + 1) {
            StackPush(stack, left);
            StackPush(stack, baseIndex - 1);
        }
        if (baseIndex < right - 1) {
            StackPush(stack, baseIndex + 1);
            StackPush(stack, right);
        }
        while (!StackEmpty(stack)) {
            right = StackPop(stack);
            left = StackPop(stack);
            baseIndex = partition(arr, left, right);
            if (baseIndex > left + 1) {
                StackPush(stack, left);
                StackPush(stack, baseIndex - 1);
            }
            if (baseIndex < right - 1) {
                StackPush(stack, baseIndex + 1);
                StackPush(stack, right);
            }
        }
        StackDestroy(stack);
}

void QuickSortFrame(int* arr, int n, int (*partition)(int*, int, int), bool is_recursive) {
    if (n <= 0) {
        return;
    }
    if (is_recursive) {
        // 递归实现
        QuickSort(arr, n, partition);
    } else {
        // 非递归实现
        QuickSortNor(arr, n, partition);
    }
}

// 内省排序 Introsort(introspective sort)
int Partition5(int* arr, int left, int right) {
    // 三数取中法选择基准值
    // 不使用midIndex = (right + left) / 2 是为了尽可能减小运算过程数据峰值，避免越界
    int midIndex = left + (right - left) / 2;
    if (arr[left] > arr[right]) {
        SWAP(int, arr[right], arr[left]);
    }
    if (arr[midIndex] > arr[right]) {
        SWAP(int, arr[midIndex], arr[right]);
    }
    if (arr[left] > arr[midIndex]) {
        SWAP(int, arr[left], arr[midIndex]);
    }

    int base = arr[midIndex];
    // arr[left]一定比arr[mid]小，所以直接从索引left + 1开始执行Partition2
    ++left;
    // 这里由于是宏替换所以不能将++left塞入SWAP中，但如果是宏函数就可以
    SWAP(int, arr[left], arr[midIndex]);
    while (left < right) {
        while (left < right && base <= arr[right]) {
            --right;
        }
        arr[left] = arr[right];
        while (left < right && arr[left] <= base) {
            ++left;
        }
        arr[right] = arr[left];
    }
    arr[left] = base;
    return left;
}

void InsertSortAtIntroSort(int* arr, int left, int right) {
    for (int i = left; i <= right; i++) {
        int min = arr[i];
        int j = i - 1;
        for (;j >= 0; j--) {
            if (arr[j] > min) {
                arr[j + 1] = arr[j];
            } else {
                break;
            }
        }
        arr[j + 1] = min;
    }
}

void HeapifyAtIntroSort(int* arr, int parent, int end) {
    int child = parent * 2 + 1;
    while (child <= end) {
        if (child < end && arr[child + 1] > arr[child]) {
            ++child;
        }
        if (arr[child] > arr[parent]) {
            SWAP(int, arr[child], arr[parent]);
            parent = child;
            child = parent * 2 + 1;
        } else {
            break;
        }
    }
}

void IntroSortInner(int* arr, int left, int right, int maxDepth) {
    // 小规模数据使用插入排序
    if (right - left < 16) {
        InsertSortAtIntroSort(arr, left, right);
        return;
    }

    // 递归深度过大时使用堆排序
    if (maxDepth == 0) {
        for (int i = (right - left - 1) / 2; i >= 0; i--) {
            HeapifyAtIntroSort(arr, i, right - left);
        }

        for (int i = right - left; i >= 0; i--) {
            SWAP(int, arr[left], arr[left + i]);
            HeapifyAtIntroSort(arr, 0, i);
        }
        return;
    }

    // 快速排序
    int baseIndex = Partition5(arr, left, right);
    IntroSortInner(arr, left, baseIndex - 1, maxDepth - 1);
    IntroSortInner(arr, baseIndex + 1, right, maxDepth - 1);
}

void IntroSort(int* arr, int n) {
    int maxDepth = (int)(2 * log2(n));
    IntroSortInner(arr, 0, n - 1, maxDepth);
}

